\section{Motores comerciales}

En esta secci'on se explayan los funcionamientos generales y ajustes particulares de dos motores de bases de datos muy populares, uno privado y 
distrubuci'on bajo licencia llamado Oracle Database y otro libre y de c'odigo abierto llamado PostgreSQL.

\subsection{Oracle}
Oracle Database es un motor de base de datos de uso bajo licencia y c'odigo cerrado que surgi'o a fines de la d'ecada del `70 y durante mucho
tiempo domin'o totalmente el mercado.

\subsubsection{Estructura general}
Oracle usa una modificaci'on extensiva del sistema LRU para manejo de buffers.
Un problema que se puede presentar con LRU, es que durante un \textit{table scan} de una tabla grande, 
por ejemplo una que tenga m'as bloques que los que entran en memoria, va a poner secuencialmente todos los bloques en memoria, 
vaciando la cache. Esos bloques van a arruinar una cache posiblemente muy buena, porque no se van a volver a leer pronto.
Luego, una modificaci'on que hace Oracle es poner a los bloques de un table scan al final de la cola LRU, y permitir que
usen solo una peque\~na cantidad de bloques de la cola. Esto arregla el problema que podr'ia generar un table scan.
Otro problema podría ser un \textit{index range scan} muy grande. Las hojas del \textit{b-tree} van a ser accesadas varias veces, 
y si la tabla es grande, puede arruinar el cache. Luego lo que hace Oracle es tener 3 tipos de cache, uno por cada tama\~no de objeto. 
Las hojas de un índex scan van a la cola correspondiente a objetos peque\~os. Un bloque normal ir'ia la cola por default. 
De esta manera esos bloques de índices no molestan a la operación normal del cache.

\subsubsection{Mejoras de performance}
Para mejor performance, Oracle ahora usa un algoritmo basado en \textit{touch counts}, o conteo de accesos. 
Cada bloque (i.e. cada buffer) tiene asociado un touch count, que determina la popularidad del objeto. 
Esto se parecer'ia a un algoritmo LFU, pero con modificaciones a describir a continuaci'on.
Primero, la cola LRU es dividida en 2 mitades, llamadas hot y cold. Estas mitades son, por default, iguales en tama\~no, pero se puede cambiar esto con el 
par'ametro \textit{\_db\_percent\_hot\_default} (el \textit{\_default} se refiere a que esta es la cola default, 
y no la de objetos muy pequeños (\textit{\_keep}) ni la de objetos muy grandes (\textit{\_recycle})).
\\
El primer cambio implementado es que un nuevo bloque se inserta en el medio de la cola LRU, y no al frente como es habitual. 
Esto se conoce como \textit{midpoint insertion}. Para prevenir que el comportamiento ``muchos inserts en un corto plazo, nada de actividad por mucho tiempo''
rompa la cache, Oracle limita la cantidad de veces que se puede aumentar un \textit{touch count}, por defecto, a una cada 3 segundos. 
Esto se puede cambiar con el par'ametro \textit{\_db\_aging\_touch\_time}.
Estos conteos no son protegidos por un latch (el t'ermino que Oracle le da a los locks), 
por tanto puede ser que dos threads intenten aumentar el touch count de un bloque, y termine siendo como que s'olo uno lo hizo.
\\
A diferencia de un LFU normal, el incrementar un \textit{touch count} no hace que un buffer se mueva al extremo m'as usado de la cola. 
Es m'as, no hace que se mueva en absoluto. Un bloque se mueve cuando, al intentar insertar un nuevo bloque en el cache, se busca un nuevo lugar para el bloque. 
Si en el proceso de búsqueda de bloques para sacar del cache se encuentra un bloque cuyo touch count es mayor que 2, 
se mueve el bloque hacia el extremo MRU de la cola. Asimismo, se pone su touch count en 0 al hacer esto.
\\
Cuando un buffer se mueve de la región cold a la regi'on \textit{hot}, algún otro buffer tendrá que moverse de la hot a la cold para que el balance sea el correcto 
(50\% por defecto). Luego, a este bloque que pasa de \textit{hot} a \textit{cold}, se le pone su touch count en 1.
Antes de sacar a un bloque de la cola, si el bloque fue modificado durante su estad'ia en la \textit{cache}, est'a \textit{dirty} y 
debe ser escrito a disco antes de sacarlo de la cola. Si el bloque no fue modificado puede ser removido de la cola normalmente.

\subsubsection{Fuentes}
\begin{itemize}
\item http://www.adp-gmbh.ch/ora/concepts/cache.html
\item http://talebzadehmich.wordpress.com/2012/03/27/buffer-management-strategy-of-oracle/
\item http://www.dbguide.net/upload/20060316/1142482749257.pdf
\end{itemize}

\subsection{PostgreSQL}
PostgreSQL es un motor de base de datos libre y de c\'odigo abierto que se distribuye bajo licencia \textit{BSD}. Su desarrollo empez'o entre fines de la d'ecada del `80 
y principio de los `90.
\\
Este motor usa una modificaci'on de las colas LRU para su manejo de buffers incluyendo un mecanismo similar al de ``conteo de touches'', 
con el agregado del concepto de ``pins''. \\
Cuando un cliente va a leer o escribir de un buffer, al buffer se le pone un ``pin'', que implica que está siendo usado. 
El cliente, al liberar el buffer, remueve el ``pin'' del buffer.\\
El proceso de pinning aumenta en 1 al conteo de accesos del buffer en cuesti'on, hasta un m'aximo de 5. 
Este conteo se usa durante la búsqueda de bloques para sacar de la cache: 
Si un bloque no est'a \textit{pinned} (o sea no est'a siendo usado actualmente), y tiene un conteo de acceso de 0, se puede sacar.
\\
Para encontrar tal bloque, PostgreSQL recorre la lista de bloques en forma circular, empezando desde el elemento menos recientemente usado. 
Por cada bloque que no est'a \textit{pinned}, el algoritmo hace esto:

\begin{verbatim}
if (bloque.conteo_accesos == 0) {
  if (bloque.dirty) {
    escribir_a_disco(bloque);
  } else {
    remover_de_cola(bloque);
} else {
  bloque.conteo_accesos = bloque.conteo_accesos - 1;
}
\end{verbatim}
Si al final de una iteraci'on entera por los bloques de la cola no pudo escribir a ninguno a disco, 
se vuelve a empezar desde el extremo que corresponde a los bloques menos recientemente usados.
\\
Una optimizaci'on para los \textit{table scans}, parecida a la de Oracle, es que los table scans no reciben acceso a todos los bloques de la cache. 
Reciben solamente un n'umero limitado, llamado un \textit{buffer ring}, al que usan de forma circular, es decir, como si fuera un "mini-cache circular" 
para ese table scan en particular, sin afectar al cache verdadero. 


\subsubsection{Fuentes}
\begin{itemize}
\item http://www.westnet.com/~gsmith/content/postgresql/InsideBufferCache.pdf
\item http://fossies.org/unix/misc/postgresql-9.1.4.tar.gz:a/postgresql-9.1.4/src/backend/storage/buffer/README
\end{itemize}

\subsection{Comparaci'on de motores, ventajas y desventajas}
En funci\'on de los an\'alisis anteriores se presenta la siguiente tabla comparativa de eficiencia de las distintas estrategias en los distintos contextos:
\begin{center}
  \begin{tabular}{ | p{4cm} | p{4cm} | p{4cm} | }
    \hline
     & \textbf{Oracle} & \textbf{PostgreSQL} \\ \hline
    \textbf{Estrategia principal} & LRU & LRU \\ \hline
    \textbf{Variante} & Movimiento de bloques s'olo al insertar & Algoritmo \textit{Second-Chance} \\ \hline
    \textbf{Ventajas} & Es muy completo y particularmente eficiente en los \textit{range index scan} & 
    El c'odigo es abierto por lo cual el \textit{memory buffer} se puede analizar y mejorar
     \\ \hline
    \textbf{Desventajas} & Al ser muy complejo y no tener disponible el c'odigo es dificil de analizar &  No es tan completo y es mas senciollo que el de Oracle\\ \hline
  \end{tabular}
\end{center}
